--- title: "min属性 潜水员" created: 2025-11-28 tags: - 算法 --- # min属性 潜水员 ## 题目 [潜水员](https://www.cnblogs.com/littlehb/p/15689906.html) 潜水员为了潜水要使用特殊的装备。 他有一个带2种气体的气缸：一个为氧气，一个为氮气。 让潜水员下潜的深度需要各种数量的氧和氮。 潜水员有一定数量的气缸。 每个气缸都有重量和气体容量。 潜水员为了完成他的工作需要特定数量的氧和氮。 他完成工作所需气缸的总重的 **最低限度** 的是多少？ 例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量： ```text 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119 ``` 如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。 你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的 **最低值**。 **输入格式** 第一行有2个整数 m，n。它们表示氧，氮各自需要的量。 第二行为整数 k 表示气缸的个数。 此后的 k 行，每行包括ai，bi，ci，3个整数。这些各自是：第 i 个气缸里的氧和氮的容量及气缸重量。 **输出格式** 仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。 **数据范围** 1≤m≤21,1≤n≤79,1≤k≤1000,1≤ai≤21,1≤bi≤79,1≤ci≤800 **输入样例**： ```text 5 60 5 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119 ``` **输出样例**： ```text 249 ``` ## 思路分析 不难发现也是一个二维限制问题 但属性有些不同 - 普通的二维背包费用问题 f(i,j,k) 表示从前i个物品中选，且花费1**不超过**j,花费2**不超过**k的 **最大** 价值 - 潜水员 f(i,j,k) 表示从前i个物品中选，且花费1**不少于**j,花费2**不少于**k的 **最小** 价值 `f[i][j][k]`，表示从前i个气缸中选取一些气缸，恰好满足至少有j升氧气和k升氮气的情况下，气缸的最小总重量 **初始化** - `dp[0][0][0] = 0`：不选取任何气缸时，没有重量，也没有氧气和氮气。 - 其他情况初始化为一个大数，例如`INT_MAX`，表示在没有选择任何气缸的情况下，不可能满足任何正的氧气或氮气需求。 ![[image-29b9623e.png]] 这样分析完 似乎与普通的二维费用背包没有区别 不可能，必然是遗漏了些什么 **考虑j−v1<0,k−v2<0的情况** 有普通的二维费用背包问题中，j,k是不能进行超载的，超过了背包就太重， 背包就 **漏** 了！ 在本题中，是 **可以超载** 的，理解一下超载是什么意思： > j:氧气还需缺少j升 > > k:氮气还需缺少k升 > > 例如：j=2,k=5,就是氧气还需要2升，氮气还需要5升，现在出现的某个气瓶，氧气20升，氮气50升，一个就可以把你的需求满足，那么：你还需要氧气多少升、氮气多少升？ **答**：不需要，都可以满足要求了，即j=0,k=0,也就是f[i−1][0][0]+w,而对于一个无欲无求的f[i−1][0][0]自然是等于0,也就是f[i][j][k]=w **状态转移方程** 对于每一个气缸i（其中i从1到k），我们可以选择它或者不选择它。如果我们选择这个气缸，那么对于每个j（氧气需求）和k（氮气需求），状态转移方程如下： `dp[i][j][k]=min(dp[i−1][j][k],dp[i−1][max(j−ai,0)][max(k−bi,0)]+ci)` - `dp[i-1][j][k]`：不选择当前气缸的情况。 - `dp[i-1][max(j-ai, 0)][max(k-bi, 0)] + ci`：选择当前气缸的情况，其中`ai`、`bi`和`ci`分别是当前气缸提供的氧气量、氮气量和重量。我们从j和k中减去当前气缸提供的量（如果`j-ai`或`k-bi`计算出来是负数，将需求量设置为0，因此用max保证至少为0），然后加上当前气缸的重量。 **目标** 遍历完成后，`dp[k][m][n]`（其中k是气缸的总数，m和n分别是所需的氧气和氮气量）就是所求的最小重量。如果某些状态无法通过选择气缸来满足氧气和氮气的需求，那么它们的值会保持为初始化的大数，这些状态不会影响最终结果。 为什么以max为属性的背包问题不需要做max(j-v,0) 而 以min为属性要考虑呢 **最大化属性（Max属性）** 在最大化属性的问题中，我们通常关注的是如何通过选择一系列物品来最大化总价值。这里的约束是背包的容量限制。 - **目标和约束**：我们希望在不超过背包容量的前提下，尽可能地增加背包中物品的总价值。 - **处理**`j-v<0`**的情况**：如果当前物品的体积`v`大于当前考虑的容量`j`（即`j-v<0`），则这个物品无法被选入背包，因为它单独就超过了背包的容量限制。在最大化问题中，这意味着对于任何超过背包容量的物品，我们简单地不选择它。这是一个直接的决策，因为选择它会违反背包容量的基本约束。 **我们在一开始就做了这件事——if(体积足够） 才考虑右边集合的情况 直接排除了 而无需考虑什么小于0再取0** **最小化属性（Min属性）** 在最小化属性的问题中，如寻找满足特定需求（比如特定量的氧气和氮气）的最小总重量，问题的性质和处理方式有所不同。 - **目标和约束**：我们需要精确满足一些外部给定的条件（例如，氧气和氮气的特定需求），同时尽可能地减少满足这些条件所需的总重量。 - **处理**`j-v<0`**的情况**：在最小化属性的问题中，`j-v<0`的处理更复杂。我们需要确保所有需求都被精确满足，这可能包括对不同物品组合的详细考虑。对于某些需求，可能不存在任何单个物品可以满足的情况，因此我们需要考虑组合物品以满足需求。在这种情况下，即使某些物品组合的部分属性（如氧气或氮气的量）超过了需求，我们也可能需要选择它们，因为这可能导致总重量的最小化。 **核心差异** - **最大化问题**：不需要特别处理`j-v<0`的情况，因为超出容量的物品自然被排除，不会对最大化目标产生贡献。 - **最小化问题**：需要详细考虑各种情况，包括`j-v<0`，因为我们的目标是找到满足特定需求的最轻重量组合，这可能涉及到对各种物品组合的仔细评估，即使某些物品单独看似不可行。 总的来说，最大化和最小化属性的背包问题在处理`j-v<0`的情况时有本质的不同，这反映了问题目标和约束条件对问题解法的影响。最大化问题简化了决策过程，因为只有在不违反容量限制的情况下才考虑增加价值。而最小化问题则需要更多地考虑如何精确满足给定的需求，即使这意味着要考虑在某些情况下似乎不可行的物品组合。 ## 代码实现 ```cpp #include using namespace std; const int N = 1010; const int M = 110; int f[N][M][M]; int n, m1, m2; //二维费用01背包-不少于维度费用，求最小代价 int main() { scanf("%d %d %d", &m1, &m2, &n); //求最小值 价值不小于 把[0][0][0]初始化成0 其他正无穷 memset(f, 0x3f, sizeof f); f[0][0][0] = 0; for (int i = 1; i <= n; i++) { int v1, v2, w; scanf("%d %d %d", &v1, &v2, &w);// 输入每个气缸的氧气量，氮气量和重量 for (int j = 0; j <= m1; j++) for (int k = 0; k <= m2; k++) { f[i][j][k] = f[i - 1][j][k];// 不选择当前气缸 // 选择当前气缸 f[i][j][k] = min(f[i][j][k], f[i-1][max(0, j - v1)][max(0, k - v2)] + w); // 选择当前气缸 } } printf("%d\n", f[n][m1][m2]); return 0; } ``` ```cpp #include using namespace std; const int N = 22, M = 80; int n, m, K; int f[N][M]; int main() { cin >> n >> m >> K; memset(f, 0x3f, sizeof f); f[0][0] = 0; while (K--) { int v1, v2, w; cin >> v1 >> v2 >> w; for (int i = n; i >= 0; i--) for (int j = m; j >= 0; j--) f[i][j] = min(f[i][j], f[max(0, i - v1)][max(0, j - v2)] + w); } cout << f[n][m] << endl; return 0; } ``` ## 同类题型 ## 视频讲解 --- ⬅️ [[分组背包问题|分组背包问题]] 🏠 [[00-刷题理模型]] ➡️ [[加维度背包问题练习|加维度背包问题练习]]